package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 回溯 解决方式
 * <p>
 * <p>
 * {2,3,4,5,6,7}  target = 8
 * <p>
 * for(){
 * 2(接受到 回来 null 的话 就不 add ,有的话就加上去)
 * <p>
 * 2 ,3 ,4 ,5 ,6, 7
 * <p>
 * }
 */


public class D_39 {
    public static void main(String[] args) {
        int[] list = {2, 3, 5};
        List<List<Integer>> list1 = new D_39().combinationSum(list, 8);
        System.out.println(list1);
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(candidates);
        getArg(candidates, target, new ArrayList<>(), list,0);
        return list;
    }

    public void getArg(int[] candidates, int target, List<Integer> list, List<List<Integer>> lists,int i) {
        for (int i1 = i; i1 < candidates.length; i1++) {
            if (target - candidates[i1] > 0) {
                list.add(candidates[i1]);
                getArg(candidates, target - candidates[i1], list, lists,i1);
                list.remove(list.size() - 1);
            } else if (target - candidates[i1] == 0) {
                list.add(candidates[i1]);
                lists.add(new ArrayList<>(list));
                list.remove(list.size() - 1);
                return;
            }
        }

//        for (int candidate : candidates) {
//            if (target - candidate > 0) {
//                list.add(candidate);
//                getArg(candidates, target - candidate, list, lists,);
//                list.remove(list.size() - 1);
//            } else if (target - candidate == 0) {
//                list.add(candidate);
//                ArrayList<Integer> objects = new ArrayList<>(list);
//                list.remove(list.size() - 1);
//                lists.add(objects);
//                return;
//            }
//        }
    }
}
